package leetcode101_xqzhao

// TODO 下一个排列 【-】 脑筋急转弯

func nextPermutation(nums []int) {
	n := len(nums)

	// 寻找第一个小于右邻居的数
	curr := n - 1
	for ; curr > 0 && nums[curr] <= nums[curr-1]; curr-- {
	}
	if curr == 0 { // 没有小于右邻居的数, 直接全部反转
		reverse(nums, 0, n-1)
	} else {
		// 寻找第一个大于 nums[curr-1] 的数
		i := n - 1
		for i >= 0 && nums[i] <= nums[curr-1] {
			i--
		}
		nums[i], nums[curr-1] = nums[curr-1], nums[i]
		reverse(nums, curr, n-1) // 后面的递减序列反转
	}
}

func reverse(nums []int, left int, right int) {
	for i := 0; i <= (right-left)/2; i++ {
		nums[left+i], nums[right-i] = nums[right-i], nums[left+i]
	}
}
